МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» Кафедра ЕОМ / Звіт лабораторної роботи №2 «Дерева прийняття рішень» з дисципліни: «Комп'ютерні системи штучного інтелекту»  Мета роботи : навчитися будувати дерева рішень на базі алгоритму ID3 тавирішувати проблему суперечливості даних у таблицях прийняття рішень.Теоретичні відомості Для проведення досліджень або для комерційних цілей часто створюються дужевеликі бази даних. Іноді ці бази даних стають настільки великими, що їх опрацювання йінтерпретація даних людиною майже не можлива. В наслідок цього утворюється розбіжністьміж появою нових даних і їх розумінням. Цю розбіжність можуть допомогти подолатиінструменти й методи для виявлення нових, раніше невідомих закономірностей, схованих у даних. Ця проблематика спричинила розвиток нових галузей штучного інтелекту —дослідження даних (Data mining), видобування знань з баз даних (Knowledge dіscovery іndatabases) та машинного навчання (Machine learning).Крім цього постає велика кількість задач прийняття рішень, коли потрібно відноситинові об’єкти до певного класу. Такі задачі прийняття рішень щодо нових об’єктів вимагаютьпошуку правил, які дозволяють класифікувати об’єкт. Такий пошук правил належить докласу задач машинного навчання, і відбувається на основі вже наявної інформації прооб’єкти, яка представляється у вигляді таблиці прийняття рішень. Дерева рішень (decision trees) Алгоритми дерев рішень – одні з найшвидших і ефективніших в області KDD, черезщо одержали значне поширення. Зазвичай їх використовують для задач класифікації данихабо для задач апроксимації заданої булівської функції. Їхня обчислювальна складністьвизначається головним чином типом критерія розщеплення. У багатьох випадках часзнаходження критерію розщеплення лінійно залежить від кількості полів. Залежність часурішення від кількості записів n часто лінійна, або близька до неї (n×log(n)).Переваги використання дерев рішень: – швидкий процес навчання; – генерування правил в областях, де експертові важко формалізувати свої знання;– побудова правил природною мовою; – інтуїтивно зрозуміла класифікаційна модель; – висока точність прогнозу, порівняно з іншими методами (статистичними, нейромережевими).Проте виразна сила дерев рішень часто недостатня для опису складних правил, щозустрічаються в реальних даних. Це приводить до неминучості побудови дуже великих (ітому незрозумілих) дерев. Інша характерна для систем KDD складність пов'язана з виборомкритерію для зупинки подальшого дроблення на групи. Дуже важко знайти компроміс міжточністю результуючого правила, що виходить, і його статистичною значимістю.Постановка задачі для використання алгоритмів побудови дерев прийняття рішеньможе приймати наступний вигляд. Необхідно створити економічну конструкцію , яка бописувала (булівську) функцію, що складається з множини випадків, кожен з якихописується кінцевим набором дискретних атрибутів. Алгоритм ID3 ID3(A,S,J ) 1. Створити корінь дерева. 2. Якщо S виконується на всіх елементах А, поставити в корінь мітку 1 і вийти.3. Якщо S не виконується на жодному з елементів А, поставити в корінь мітку 0 і вийти.4. Якщо Q=0, то : а) якщо S виконується на половині чи більшій частині А, поставити в корінь мітку 1 івийти;б) якщо S не виконується на більшій частині А, поставити в корінь мітку 0 і вийти.5. Вибрати Q ÎJ , для якого Gain(A,Q) Завдання: Нам потрібно дізнатися чи переможе футбольна команда матч. Виконання: Нам відомо, що це залежить від наступних параметрів: n положення суперника у турнірній таблиці (вище або нижче); n чи вдома відбувається матч; n чи пропускає матч хтось із лідерів; n чи падає дощ. На базі цих параметрів була зібрана така статистика :Таблиця 1. Статистика попередніх ігор / Отже, інформацію про попередні ігри ми помістили у відношення, де атрибутами єпараметри, що впливають на якість гри. Атрибут Перемога називається атрибутомприйняття рішення. Спробуємо побуду...